/*
 * Given a string, find the length of the longest substring without repeating
 * characters. For example, the longest substring without repeating letters for
 * "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring
 * is "b", with the length of 1.
 */

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (!s.length()) return 0;
        // array tracking position of letters
        int spos, len, maxlen;
        vector<int> tarray(256, -1);
        spos = len = maxlen = 0;
        for (int curpos = 0; curpos < s.length(); curpos++) {
            int idx = s[curpos];
            if (tarray[idx] >= spos) { // duplicate within cur substr
                if (len > maxlen) maxlen = len;
                // set new start to last duplicate char plus one
                len = len - (tarray[idx] - spos);
                spos = tarray[idx] + 1;
            } else len ++;
            tarray[idx] = curpos;
        }
        if (len > maxlen) maxlen = len; // last substr
        return maxlen;
    }
};

#if 0
#include <iostream>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (!s.length()) return 0;
        // array tracking position of letters
        int spos, len, maxlen;
        int tarray[26];
        for (int i = 0; i < 26; i++) tarray[i] = -1;
        spos = len = maxlen = 0;
        for (int curpos = 0; curpos < (int)s.length(); curpos++) {
            int idx = s[curpos]-'a';
            if (tarray[idx] >= 0) {
                // duplicate detected, record current substr
                if (len > maxlen) maxlen = len;
                // reset tarray for chars excluded from new substr
                for (int j = spos; j < tarray[idx]; j++) {
                    int tmpidx = s[j]-'a';
                    tarray[tmpidx] = -1;
                }
                // set new start to last duplicate char plus one
                len = len - (tarray[idx] - spos);
                spos = tarray[idx] + 1;
            } else {
                len ++;
            }
            tarray[idx] = curpos;
        }
        if (len > maxlen) maxlen = len;
        return maxlen;
    }
};

int main() {
    Solution sol;
    string s("wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco");

    int maxlen = sol.lengthOfLongestSubstring(s);
    cout << "maxlen = " << maxlen << endl;

    return 0;
}
#endif
